/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：DisjointSet.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-10
Function List ：
Description   ：Disjoint Set
******************************************************/

#include "DisjointSet.h"

void Initialize(DisjSet S) {
    int i;

    for (i = NumSets; i > 0; --i) {
        S[i] = 0;
    }
}

/* Assumes Root1 and Root2 are roots */
/* union is a C keyword, so this routine */
/* is named SetUnion */
void SetUnion(DisjSet S, SetType Root1, SetType Root2) {
    /* Root2 is deeper set */
    if (S[Root2] < S[Root1]) {
        S[Root1] = Root2;  /* Make Root2 new root */
    } else {
        /* Same height, so update */
        if (S[Root1] == S[Root2]) {
            --S[Root1];
        }

        S[Root2] = Root1;
    }
}

SetType Find(ElementType X, DisjSet S) {
    if (S[X] <= 0) {
        return X;
    } else {
        return S[X] = Find(S[X], S);
    }
}

// EOF

